1. Field of the Invention
The present invention relates to an information processing technique for processing data elements in nodes connected to each other between two data streams each having a plurality of nodes.
2. Description of the Related Art
An application which compares data elements held by nodes in two data streams each having a plurality of nodes is available. For example, processing which makes comparisons by a round-robin method when it is determined whether or not elements of a first data stream having a plurality of data match at least one of elements of a second data stream is known. Such application compares data elements in the first data stream which shifts data elements in a given direction, and the second data stream which shifts data elements in a direction opposite to the given direction. However, as will be described later, a case in which comparisons of data elements in respective nodes may often not normally work in the two data streams which shift data elements in opposite directions occurs.
Japanese Patent No. 3588487 (patent literature 1) describes a two-way pipeline technique (counterflow pipeline technique) which compares respective data elements in respective stages of pipelines in pipeline data streams of two different types, which shift data elements in opposite directions. This patent literature 1 discloses one solution to the case in which comparisons of data elements in respective nodes do not normally work.
The case in which comparisons of data elements do not normally work in this application will be described below with reference to FIGS. 13A to 13C. FIGS. 13A to 13C partially show two pipeline circuits which shift data elements in opposite directions. A first pipeline on the lower side shifts data elements from the left side on the plane of the drawing as “upstream” toward the right side on the plane of the drawing as “downstream”. On the other hand, a second pipeline on the upper side shifts data elements from the right side on the plane of the drawing as “upstream” toward the left side on the plane of the drawing as “downstream”.
13a-1 to 13a-3 of FIGS. 13A to 13C show a case in which comparisons of data elements are normally done, and the aforementioned problem is not posed. In this case, the first pipeline operates to shift data elements, and the second pipeline stops not to shift data elements. 13a-1 of FIG. 13A shows a state at time [T], 13a-2 of FIG. 13B shows a state at time [T+1] after an elapse of a predetermined time period from time [T], and 13a-3 of FIG. 13C shows a state at time [T+2] after a further elapse of a predetermined time period from time [T+1].
Now assume that the first pipeline operates to shift data elements W, A(0), A(1), A(2), B, and C held in pipeline stages from the left side on the plane of the drawing as “upstream” toward the right side on the plane of the drawing as “downstream”. Note that the data elements A(0), A(1), and A(2) are described by attaching (0), (1), and (2) to A to distinguish them from each other for the sake of descriptive convenience, but they can be considered as those equivalent to other data. Corresponding stages of the first and second pipelines are connected to each other via determination stages 901 to 904 each of which determines whether or not two data elements are the same by comparison.
At time [T] in 13a-1 of FIG. 13A, the determination results of the respective stages are as follows in turn from “downstream” of the first pipeline. The determination stage 901 on the most downstream side of the first pipeline compares data elements W and A. In this case, since the two data elements do not match, the stage 901 determines <false>. The subsequent determination stages 902 to 904 respectively compare data elements A(0) and Z, data elements A(1) and Y, and data elements A(2) and X. Since these data elements do not match, these stages determine <false>.
At time [T+1] of 13a-2 of FIG. 13B after an elapse of a time period, the data elements in the first pipeline shift by one stage to “downstream”. The determination results in the determination stages 901 to 904 are as follows in turn from “downstream” of the first pipeline. The determination stage 901 compares data elements A(0) and A. Since these two data elements match, the stage 901 determines <true>. The subsequent determination stages 902 to 904 respectively compare data elements A(1) and Z, data elements A(2) and Y, and data element B and X. Since these data elements do not match, these stages determine <false>.
At time [T+2] of 13a-3 of FIG. 13C after a further elapse of a time period, the data elements in the first pipeline further shift by one stage to “downstream”. The determination results in the determination stages 901 to 904 are as follows in turn from “downstream” of the first pipeline. The determination stage 901 compares data elements A(1) and A. Since these two data elements match, the stage 901 determines <true>. The subsequent determination stages 902 to 904 respectively compare data elements A(2) and Z, data elements B and Y, and data element C and X. Since these data elements do not match, these stages determine <false>.
As described above, the data elements in the first pipeline shift around the stages as elapses of time periods. The data element A located on “upstream” of the second pipeline can be normally compared with the data elements A(0) and A(1) in the first pipeline. In this way, when one of the first and second pipeline operates, and the other stops, comparisons of the data elements are normally done.
13b-1 to 13b-3 of FIGS. 13A to 13C show a case in which both the first and second pipelines operate. 13b-1 to 13b-3 of FIGS. 13A to 13C show states at the same times as 13a-1 to 13a-3 of FIGS. 13A to 13C. Since the operations of the first pipeline are the same as those in 13a-1 to 13a-3 of FIGS. 13A to 13C, a description thereof will not be repeated. On the other hand, the operations of the second pipeline are different from those in 13a-1 to 13a-3 of FIGS. 13A to 13C. That is, the second pipeline shifts data elements X, Y, Z, A, B, and C held in pipeline stages from the right side on the plane of the drawing as “upstream” toward the left side on the plane of the drawing as “downstream”. The determination results of the determination stages in the corresponding stages of the first and second pipelines will be explained below in the same manner as in 13a-1 to 13a-3 of FIGS. 13A to 13C.
At time [T] of 13b-1 of FIG. 13A, the determination results of the respective stages are as follows in turn from “downstream” of the first pipeline. The determination stage 901 on the most downstream side of the first pipeline compares data elements W and A. In this case, since the two data elements do not match, the stage 901 determines <false>. The subsequent determination stages 902 to 904 respectively compare data elements A(0) and Z, data elements A(1) and Y, and data elements A(2) and X. Since these data elements do not match, these stages determine <false>.
At time [T+1] of 13b-2 of FIG. 13B after an elapse of a time period, the data elements in the first and second pipelines shift by one stage to their downstream sides. The determination results in the determination stages 901 to 904 are as follows in turn from “downstream” of the first pipeline. The determination stage 901 compares data elements A(0) and B. Since these two data elements do not match, the stage 901 determines <false>. The next determination stage 902 compares data elements A(1) and A. Since these two data elements match, the stage 902 determines <true>. The subsequent determination stages 903 and 904 respectively compare data elements A(2) and Z and data element B and Y. Since these data elements do not match, these stages determine <false>.
At time [T+2] of 13b-2 of FIG. 13B after a further elapse of a time period, the data elements in the first and second pipelines shift by one stage to their “downstream” sides. The determination results in the determination stages 901 to 904 are as follows in turn from “downstream” of the first pipeline. The determination stage 901 compares data elements A(1) and C. Since these two data elements do not match, the stage 901 determines <false> (however, A(1) has already been determined as <true> in the determination stage 902 in 13b-2 in FIG. 13B). The subsequent determination stages 902 to 904 respectively compare data elements A(2) and B, data elements B and A, and data element C and Z. Since these data elements do not match, these stages determine <false>.
As described above, when the first and second pipelines move at the same time, the data element A located on “upstream” of the second pipeline is compared with the data element A(1) of the first pipeline. However, the data elements A(0) and A(2) are never compared with the data element A of the second pipeline. For example, as can be seen from the above description, when the respective data elements of the first pipeline match at least one of the respective data elements of the second pipeline, the processes in 13b-1 to 13b-3 of FIGS. 13A to 13C cannot attain normal determination. This is because since both the first and second pipelines move in the opposite directions, the relative moving speed of the two pipelines doubles.
In practice, in the case of 13a-1 to 13a-3 of FIGS. 13A to 13C, only the comparisons of the data elements W, A(0), and A(1) of the first pipeline are completed during an interval between times [T] to [T+2]. By contrast, in the case of 13b-1 to 13b-3 of FIGS. 13A to 13C, the comparisons of the data elements W, A(0), A(1), A(2), and B of the first pipeline are completed. In this manner, the case of 13b-1 to 13b-3 of FIGS. 13A to 13C can shorten a determination time period compared to the case of 13a-1 to 13a-3 of FIGS. 13A to 13C, but it causes comparison errors of data elements.
The technique of Japanese Patent No. 3588487 solves this problem by shifting data elements in an irregular schedule according to an execution-scheduled operation with respect to a specific stage through which data elements pass when they shift, and data elements. More specifically, the stage statuses of the respective stages of the first and second pipelines are monitored. Then, in a specific stage which poses this problem, shifting of data elements in the pipelines in the two directions is stopped. After completion of a comparison, shifting of data elements of that specific stage is permitted. As a result of this devise, related data elements on the pipelines in the two directions can be avoided from passing without undergoing determination before completion of the comparison.
However, with this configuration, since the specific stage which may pose the problem requires a stop operation, completion of a comparison, and a shift operation of data elements, data elements repeat shifting and stopping in an irregular schedule in correspondence with respective stage statuses. Due to repetition of such irregular schedule, pipelines for data processing are disturbed, thus interfering with improvement of a throughput as an advantage to be obtained when the pipeline configuration is adopted.
On the other hand, as the best application fields when the aforementioned data processing technique is used, an image processing field and graphics processing field which execute high-speed data processing of a very large number of data elements in the pipeline configuration are known. In recent years, in such fields, various kinds of image processing are required to enhance image quality and functions of products. For example, time-division multiplexing image processing is concurrently applied to a plurality of contents (images, video pictures), and a plurality of translucent texture data are superimposed. Such image processing normally reads out and processes required image data and video data from an external memory such as a DRAM. In this case, it is a common practice to acquire data from the external memory via a cache apparatus.
However, in case of the time-division multiplexing image processing and the processing for superimposing a plurality of translucent textures, it is required to simultaneously and parallelly process various image data and video data, and image data or video data as one target data is intermittently acquired from the external memory. When image data and video data as various target data are intermittently acquired from the external memory in the general implementation of a cache technique, cache conflicts frequently occur, thus considerably lowering a cache performance. In order to avoid such cache conflicts, the number of ways of cache tags may be increased. However, when there are many ways in the general implementation of a cache technique, the number of logic stages of selectors in determination stages increases, and it becomes difficult to allow timings to converge in respective stages. For this reason, it is difficult to perform operations at a high operating frequency. Also, by increasing the number of ways, replace control at the time of cache conflicts is complicated, and it is difficult to implement the cache technique.